package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;

import java.util.ArrayList;
import java.util.Scanner;

/*
给定整数序列a1,a2,...,an,判断是否可以从中选出若干数,使它们的和恰好为k.

    1≤ n ≤20

    -10^8 ≤ ai ≤ 10^8

    -10^8 ≤  k ≤ 10^8

样例:

输入

    n=4
    a={1,2,4,7}
    k=13
输出:

    Yes (13 = 2 + 4 + 7)

 */
public class hDFS_部分和by回溯and剪枝 {
	public static void main(String[] args) {
		hDFS_部分和by回溯and剪枝 test = new hDFS_部分和by回溯and剪枝();
		test.useDFS_partSum();
	}
	
	/**
	 * 前置方法
	 */
	public void useDFS_partSum() {
		Scanner scanner = new Scanner(System.in);
		int length = scanner.nextInt();
		int[] arr = new int[length];
		ArrayList<Integer> savedElements = new ArrayList<Integer>();
		for (int i = 0; i < length; i++) {
			arr[i] = scanner.nextInt();
		}
		int currentSum = scanner.nextInt();
		int originSum = currentSum;
		DFS_partSum(arr, currentSum, 0, savedElements, originSum);
	}
	
	/**
	 * 递归形式
	 * @param arr
	 * @param sum
	 * @param current
	 */
	public void DFS_partSum(int[] arr, int sum, int current, ArrayList<Integer> savedElements, int originSum) {
		if (sum == 0) {//递归，有效结果的出口
			System.out.print("Yes (" + originSum + " = ");
			for (int i = 0; i < savedElements.size(); i++) {
				System.out.print(savedElements.get(i) + (i == savedElements.size() - 1 ? "" : " + "));
			}
			System.out.println(")");
			System.exit(0);
		}
		if (sum < 0 || current == arr.length) {
			return;//递归无效结果的出口
		}
		DFS_partSum(arr, sum, current + 1, savedElements, originSum);//首先尝试，不要arr[current]这个数的情况下，去凑sum
		
		savedElements.add(arr[current]);//因为要arr[current]，所以保存arr[current]
		DFS_partSum(arr, sum - arr[current], current + 1, savedElements, originSum);//然后尝试，要arr[current]这个数
		savedElements.remove(savedElements.size() - 1);//因为是递归尝试，所以要有回溯；这里删除新加入的元素，也就是第savedElements.size() - 1个元素
	}
}
